package com.cat.dynamicPlanning;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeSet;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-total-reward-using-operations-i/description/
 * @create 2025/9/1 20:17
 * @since JDK17
 */

public class Solution46 {

    public int maxTotalReward03(int[] nums) {
        int n = nums.length, ans = 0, max = Arrays.stream(nums).max().getAsInt(), m = max * 2 + 1;
        boolean[] dp = new boolean[m];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= ans && j < nums[i]; j++) {
                if (dp[j]) {
                    dp[j + nums[i]] = true;
                    ans = Math.max(ans, j + nums[i]);
                }
            }
        }
        return ans;
    }

    public int maxTotalReward02(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(0);
        Arrays.sort(nums);
        int ans = 0;
        for (int num : nums) {
            List<Integer> list = new ArrayList<>();
            for (Integer val : set) {
                if (val >= num) {
                    break;
                }
                list.add(val + num);
                ans = Math.max(ans, val + num);
            }
            set.addAll(list);
        }
        return ans;
    }
}
